package LeetCode.month01.day18;

import java.util.HashMap;

public class No124 {
    int maxnum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxnum;
    }
    public int dfs(TreeNode node){
        if(node==null) return 0;
        int leftmax = Math.max(dfs(node.left),0);
        int rightmax = Math.max(dfs(node.right),0);
        maxnum = Math.max(maxnum,leftmax+rightmax+node.val);
        return node.val+Math.max(leftmax,rightmax);
    }
}
